|
In the mathematical field of graph theory, a graph ''G'' is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices ''u''1—''v''1 and ''u''2—''v''2 of ''G'', there is an automorphism :''f'' : ''V''(''G'') → ''V''(''G'') such that :''f''(''u''1) = ''u''2 and ''f''(''v''1) = ''v''2. In other words, a graph is symmetric if its automorphism group acts transitively upon ordered pairs of adjacent vertices (that is, upon edges considered as having a direction). Such a graph is sometimes also called 1-arc-transitive〔 or flag-transitive. By definition (ignoring ''u''1 and ''u''2), a symmetric graph without isolated vertices must also be vertex transitive.〔 Since the definition above maps one edge to another, a symmetric graph must also be edge transitive. However, an edge-transitive graph need not be symmetric, since ''a''—''b'' might map to ''c''—''d'', but not to ''d''—''c''. Semi-symmetric graphs, for example, are edge-transitive and regular, but not vertex-transitive. Every connected symmetric graph must thus be both vertex-transitive and edge-transitive, and the converse is true for graphs of odd degree.〔 However, for even degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric.〔Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.〕 Such graphs are called half-transitive. The smallest connected half-transitive graph is Holt's graph, with degree 4 and 27 vertices.〔〔.〕 Confusingly, some authors use the term "symmetric graph" to mean a graph which is vertex-transitive and edge-transitive, rather than an arc-transitive graph. Such a definition would include half-transitive graphs, which are excluded under the definition above. A distance-transitive graph is one where instead of considering pairs of adjacent vertices (i.e. vertices a distance of 1 apart), the definition covers two pairs of vertices, each the same distance apart. Such graphs are automatically symmetric, by definition.〔 A ''t''-arc is defined to be a sequence of ''t''+1 vertices, such that any two consecutive vertices in the sequence are adjacent, and with any repeated vertices being more than 2 steps apart. A ''t''-transitive graph is a graph such that the automorphism group acts transitively on ''t''-arcs, but not on (''t''+1)-arcs. Since 1-arcs are simply edges, every symmetric graph of degree 3 or more must be ''t''-transitive for some ''t'', and the value of ''t'' can be used to further classify symmetric graphs. The cube is 2-transitive, for example.〔 ==Examples== Combining the symmetry condition with the restriction that graphs be cubic (i.e. all vertices have degree 3) yields quite a strong condition, and such graphs are rare enough to be listed. The Foster census and its extensions provide such lists.〔Marston Conder, ''(Trivalent symmetric graphs on up to 768 vertices ),'' J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63〕 The Foster census was begun in the 1930s by Ronald M. Foster while he was employed by Bell Labs,〔Foster, R. M. "Geometrical Circuits of Electrical Networks." ''Transactions of the American Institute of Electrical Engineers'' 51, 309–317, 1932.〕 and in 1988 (when Foster was 92〔) the then current Foster census (listing all cubic symmetric graphs up to 512 vertices) was published in book form.〔"The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0-919611-19-2〕 The first thirteen items in the list are cubic symmetric graphs with up to 30 vertices〔Biggs, p. 148〕〔Weisstein, Eric W., "(Cubic Symmetric Graph )", from Wolfram MathWorld.〕 (ten of these are also distance transitive; the exceptions are as indicated): Other well known cubic symmetric graphs are the Dyck graph, the Foster graph and the Biggs–Smith graph. The ten distance-transitive graphs listed above, together with the Foster graph and the Biggs–Smith graph, are the only cubic distance-transitive graphs. Non-cubic symmetric graphs include cycle graphs (of degree 2), complete graphs (of degree 4 or more when there are 5 or more vertices), hypercube graphs (of degree 4 or more when there are 16 or more vertices), and the graphs formed by the vertices and edges of the octahedron, icosahedron, cuboctahedron, and icosidodecahedron. The Rado graph forms an example of a symmetric graph with infinitely many vertices and infinite degree. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Symmetric graph」の詳細全文を読む スポンサード リンク
|